package ZS1;

/**
 * 青蛙跳台阶问题
 */
public class Main5 {

    public static void main(String[] args) {
        int res = JumpFloor2(8);
        System.out.println(res);
    }

    // case1: 递归法,每次可以跳1级或2级
    public static int JumpFloor1(int n){
        if(n == 0) return 0;
        if(n == 1) return 1;
        if(n == 2) return 2;
        return JumpFloor1(n-1) + JumpFloor1(n-2);
    }


    // case2: 非递归,每次可以跳1级或2级
    public static int JumpFloor2(int n){
        if(n == 0) return 0;
        if(n == 1) return 1;
        if(n == 2) return 2;

        int pre1 = 1;
        int pre2 = 2;
        for (int i = 3; i <= n ; i++) {
            int cur = pre1 + pre2;
            pre1 = pre2;
            pre2 = cur;
        }
        return pre2;
    }

    // case3: 一次可以跳1、2、...n级台阶
    /*
    * f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(1) + f(0)
    * f(n-1) = f(n-2) + f(n-3) + ... + f(1) + f(0)
    * ===> f(n) = f(n-1)+f(n-1) = 2*f(n-1)
    * */
    public static int JumpFloor3(int n){
        if(n == 0) return 0;
        if(n == 1) return 1;
        if(n == 2) return 2;
        return 2*JumpFloor3(n-1);

    }

    //case4: 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上m级。
    // 求该青蛙跳上一个n级的台阶总共有多少种跳法。
    public static int JumpFloor4(int n,int m){
        if(n > m){
            //   f(n) =  f(n-1) + f(n-2) + f(n-3) + ... + f(n-m)
            //   f(n-1) =   f(n-2) + f(n-3) + ... + f(n-m) + f(n-m-1)
            //   化简得：f(n) = 2f(n-1) - f(n-m-1)
            return 2*JumpFloor4(n-1,m) - JumpFloor4(n-m-1,m);
        }else{ // 当小于等于m的时候就是case3情况
            if(n<=1){
                return 1;
            }else{
                return 2*JumpFloor4(n-1,n);
            }
        }
    }

}
